{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": true
   },
   "source": [
    "<h1>目录<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#需求\" data-toc-modified-id=\"需求-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>需求</a></span></li><li><span><a href=\"#思想\" data-toc-modified-id=\"思想-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>思想</a></span></li><li><span><a href=\"#实现\" data-toc-modified-id=\"实现-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>实现</a></span></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 需求\n",
    "```\n",
    "给定一个二叉树，判断其是否是一个有效的二叉搜索树。\n",
    "\n",
    "一个二叉搜索树具有如下特征：\n",
    "\n",
    "    节点的左子树只包含小于当前节点的数。\n",
    "    节点的右子树只包含大于当前节点的数。\n",
    "    所有左子树和右子树自身必须也是二叉搜索树。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入:\n",
    "    2\n",
    "   / \\\n",
    "  1   3\n",
    "输出: true\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入:\n",
    "    5\n",
    "   / \\\n",
    "  1   4\n",
    "     / \\\n",
    "    3   6\n",
    "输出: false\n",
    "解释: 输入为: [5,1,4,null,null,3,6]。\n",
    "     根节点的值为 5 ，但是其右子节点值为 4 。\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 思想\n",
    "1. 二叉搜索树的特点是:node.left < node < node.right\n",
    "1. 可以使用stack来按照node.right,node,node.left的顺序入栈\n",
    "1. 依次pop一项,如果先pop的item小鱼后pop的,则有:node.left < node < node.right不成立,返回False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        prev = -float(\"inf\")\n",
    "        stack = [(1, root)]\n",
    "        while stack:\n",
    "            p = stack.pop()\n",
    "            if not p[1]:\n",
    "                continue\n",
    "            if p[0] == 0:\n",
    "                if p[1].val <= prev:\n",
    "                    return False\n",
    "                prev = p[1].val\n",
    "            else:\n",
    "                stack.append((1, p[1].right))\n",
    "                stack.append((0, p[1]))\n",
    "                stack.append((1, p[1].left))\n",
    "        return True       "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "base"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "目录",
   "title_sidebar": "大纲",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
